package com.heima.se.hashmap;

/*
    1. HashMap的底层/工作原理?    -- HashMap底层数据结构是什么?数据怎么保存？怎么查找？存满了怎么扩容？
    答： a. HashMap底层数据结构是哈希表结构：
                在jdk1.8以前，哈希表 = 数组 + 链表
                在jdk1.8开始，哈希表 = 数组 + 链表 + 红黑树


         b. hashMap存储数据的过程：
              1. hashMap通过put方法添加数据，底层调用：putVal进行添加
              2. 调用putVal添加时，会先对key进行二次哈希运算：(h = key.hashCode()) ^ (h >>> 16)，为了确保key尽可能的散列分布
              3. 添加过程中先判断数组table是否初始化：是否为null或者长度是否为0，是则需要先对table数组进行扩容，基于：resize()
                 扩容为一个初始长度为16的数组
              4. 接下来基于算法：拿数组长度 - 1和哈希值进行二进制位与运算，计算得到本次要添加元素的索引位置
              5. 接下来判断该索引位置是否为null，如果为null则直接存入
              6. 如果该索引位置不为null,则比较双方哈希值，哈希值不同，则添加到红黑树或链表中
              7. 哈希值相同，发生哈希碰撞，进一步比较equals，equals为false，则继续走afterNodeInsertion(evict)添加元素逻辑
              8. equals为true，则判断为key重复，则走afterNodeAccess(e)方法进行键相同，值覆盖逻辑。

        c. hashMap扩容机制： -- 数组扩容方法：resize()，数组扩容阈值：threshold
            1. 数组扩容：
                a. 第一次添加元素，数组table为null或者table.length为0，那么会扩容为一个初始长度为16的新数组，并设置扩容阈值threshold为：12
                   后续再扩容会直接基于上一次容量 * 2

                b.  后续随着持续往集合中添加元素，当集合中已有的元素个数size > 数组扩容阈值数threshold 时，就会触发数组扩容

                c. 当链表长度 > 8，底层会调treeifyBin方法尝试将链表树化，方法内会先判断数组长度是否满足树化最低标准：是否>= 64,
                   如果不满足则会放弃将链表转为红黑树，而是选择调用resize()方法扩容数组，从而分散链表压力。

            问： 假设数组扩容阈值：threshold = 12 ，问：是数组的12个索引位置被占用了，触发数组扩容，
                 还是说只要哈希表中添加了超过12个元素，数组就会扩容？

            2. 链表转红黑树条件：   转红黑树方法：treeifyBin() --> replacementTreeNode()
                a. 链表长度 > 8
                b. 数组长度 >= 64

            3. 红黑树转链表条件：
                a. 随着数组扩容resize()促使元素重排列，导致红黑树节点个数 <= 6 ，底层会调用 untreeify() -->  replacementNode()
                    方法，将红黑树转换为链表结构。
                c. 当我们调用remove删除集合元素时，如果删除之前，红黑树的根节点，根节点的左子节点，根节点的左孙子节点，
                    根节点的右子节点任意一个为null，都会调用 untreeify() -->  replacementNode()，将红黑树转换为链表结构。
 */

import java.util.HashMap;
import java.util.HashSet;

public class HashMapDemo1 {
    public static void main(String[] args) {

        HashMap<Student,String> map = new HashMap<>();

        for (int i = 1; i <= 9; i++) {
            map.put(new Student(),i+"");
        }


        System.out.println("map = " + map);

    }
}
